Học máy (Machine Learning)
Support Vector Machines (SVM)
Vinh, 08/2021
By Hoàng Hữu Việt
Email: viethh@vinhuni.edu.vn
Viện Kỹ thuật và Công nghệ, Đại học Vinh
Tài liệu tham khảo
Tài liệu chính
[1] Richard O.Duda, Peter E. Hart, David G.Stock. Pattern Classification, 2nd, Wiley,
2001.
[2] Vũ Hữu Tiệp, Machine Learning cơ bản, 2020
Nội dung
Máy véc-tơ hỗ trợ tuyến tính
Máy véc-tơ hỗ trợ lề mềm
Máy véc-tơ hỗ trợ hạt nhân
Ví dụ nhận dạng chữ số viết tay với SVM
Ví dụ nhận dạng ảnh mặt người với SVM
Bài tập
Giới thiệu
Thuật toán máy véc-tơ hỗ trợ được giới thiệu năm 1992
[1] B.E. Boser et al. A Training Algorithm for Optimal Margin Classifiers.
Proceedings of the Fifth Annual Workshop on Computational Learning Theory,
144-152, Pittsburgh, 1992.
Thuật toán máy véc-tơ hỗ trợ là một thuật toán được sử dụng trong
nhiều ứng dụng của học máy.
Bài toán nhận dạng chữ số viết tay
Bài toán nhận dạng ảnh mặt người
Bài toán nhận dạng vân tay
…
Máy véc-tơ hỗ trợ tuyến tính
Phân lớp dữ liệu tách biệt tuyến tính:
Tìm một đường thẳng/siêu phẳng sao cho tất cả các điểm thuộc lớp 1 (class 1)
thuộc về cùng một phía và các điểm lớp 2 (class 2) thuộc về cùng một phía.
Có vô số đường thẳng/siêu phẳng, vậy đường thẳng/siêu phẳng nào tốt nhất?
Làm thế nào để tìm được đường thẳng/siêu phẳng tốt nhất?
Class 1
Class 2
Class 1
Class 2
Class 1
Class 2
Máy véc-tơ hỗ trợ tuyến tính
Lề (margin) của một lớp được định nghĩa là khoảng cách từ các điểm
gần nhất của lớp đó tới đường thẳng/siêu phẳng phân lớp.
Tìm lề của 2 lớp bằng nhau và lớn nhất máy véc-tơ hỗ trợ tuyến tính.
Class 1
Class 2
Class 1
Class 2
Khoảng cách từ điểm
đến một siêu phẳng
,
Trong không gian 2 chiều:
Tham khảo cách tính ở phụ lục.
Máy véc-tơ hỗ trợ tuyến tính
Class 1
Class 2
Máy véc-tơ hỗ trợ tuyến tính
Giả sử mặt phân chia có phương trình
Bằng cách nhân các hệ số và với các
hằng số phù hợp, ta có thể giả sử rằng:
Điểm gần nhất của lớp 1 tới mặt phân chia
thõa mãn:
1.
Điểm gần nhất của lớp 2 tới mặt phân chia
thõa mãn:
-1.
Class 1
Class 2
Máy véc-tơ hỗ trợ tuyến tính
Giả sử tập huấn luyện gồm mẫu dữ liệu:
với
được gán nhãn là lớp +1
và -1.
Với cặp dữ liệu
, khoảng cách từ
tới mặt phẳng phân chia là:
Tìm và để lề đạt giá trị lớn nhất:
Class 1
Class 2
Máy véc-tơ hỗ trợ tuyến tính
Vì
cho những điểm biên, do vậy với mọi
ta có:
.
Bài toán SVM được đưa về bài toán tối ưu ràng buộc, tức tìm và :
với
Hoặc:
với
Đây là bài toán tối ưu bậc 2 (quadratic optimization problem) và được
giải bằng phương pháp Lagrangian Multiplers.
Với mẫu dữ liệu mới,
, nhãn dữ liệu
Máy véc-tơ hỗ trợ tuyến tính
Lập trình bằng Python ?
import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVC
X_train = np.array([[1,0], [0,1], [1,1], [0,2], [4,1], [2,2], [3,2],[1,4],[0,4]])
y_train = np.array([-1, -1, -1, -1, 1, 1, 1, 1, 1])
# SVM
model = SVC(kernel='linear', C = 1.0)
model.fit(X_train, y_train)
w = model.coef_
b = model.intercept_
print('w = ', w,'b = ',b)
z = np.array([[0,0]])
print(model.predict(z))
plt.grid(True)
plt.plot(X_train[:4, 0], X_train[:4, 1], 'ro', markersize = 8)
plt.plot(X_train[4:, 0], X_train[4:, 1], 'bs', markersize = 8)
x1 = np.linspace(-1,4)
x2 = -(w[0,0]*x1 + b)/w[0,1]
plt.plot(x1,x2, 'b')
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Class 2
Class 1
Máy véc-tơ hỗ trợ lề mềm
Nếu tập mẫu không tách biệt tuyến
tính?
Cho phép “lỗi”
x
i
trong phân lớp.
Tức là
x
i
xấp xỉ với số mẫu phân lớp
sai.
Ta cần tối thiểu
i
x
i
, với x
i
được
tính:
x
i
gọi là biến lùi,
x
i
= 0 không lỗi.
Class 1
Class 2
w
Máy véc-tơ hỗ trợ lề mềm
Tìm
x
i
để thõa mãn:
x
i
x
x
i
với
x
i
,
x
i
0 và C
là một hằng số điều khiển lỗi.
Nếu
x
i
= 0, các điểm
x
i
nằm trong
vùng an toàn.
Nếu
x
i
, các điểm
x
i
không
nằm trong vùng an toàn những vẫn
phân loại đúng.
Nếu
x
i
>1, các điểm
x
i
phân loại sai.
Class 1
Class 2
w
Máy véc-tơ hỗ trợ hạt nhân
Máy véc-tơ hỗ trợ hạt nhân (support vector machines with kernel
functions)
Tính toán trong không gian đặc trưng có độ phức tạp lớn hơn nhiều so
với không gian ban đầu.
f( )
f( )
f( )
f( )
f( )
f( )
f( )
f( )
f(.)
f( )
f( )
f( )
f( )
f( )
f( )
f( )
f( )
f( )
f( )
Feature space
Input space
Note: feature space is of higher dimension than the input space in practice
Máy véc-tơ hỗ trợ hạt nhân
Ý tưởng: các mẫu dữ liệu trong không gian ban đầu được chuyển tới
không gian đặc trưng mà trong đó các mẫu dữ liệu tách tuyến tính.
Chuyển bài toán về SVM tuyến tính/lề mềm để giải.
Φ: x→ φ(x)
Máy véc-tơ hỗ trợ hạt nhân
Một số hàm hạt nhân thường được sử dụng:
Máy véc-tơ hỗ trợ hạt nhân
Ví dụ bài toán XOR
import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVC
# XOR dataset and targets
X_train = np.array([[0, 0], [1, 1], [1, 0], [0, 1]])
y_train = np.array([0, 0, 1, 1])
fignum = 1
# fit the model
for kernel in ('sigmoid', 'poly', 'rbf'):
model = SVC(kernel = kernel, gamma = 4, coef0 = 0)
model.fit(X_train, y_train)
# plot the line, the points, and the nearest vectors to the plane
fig, ax = plt.subplots()
plt.figure(fignum, figsize=(1, 1))
plt.clf()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Máy véc-tơ hỗ trợ hạt nhân
plt.scatter(model.support_vectors_[:, 0], model.support_vectors_[:, 1], s=80, facecolors='None')
plt.plot(X_train[:2, 0], X_train[:2, 1], 'ro', markersize = 8)
plt.plot(X_train[2:, 0], X_train[2:, 1], 'bs', markersize = 8)
plt.axis('tight')
x_min = y_min = -2
x_max = y_max = 3
X, Y = np.mgrid[x_min:x_max:200j, y_min:y_max:200j]
Z = model.decision_function(np.c_[X.ravel(), Y.ravel()])
# Put the result into a color plot
Z = Z.reshape(X.shape)
plt.figure(fignum, figsize=(4, 3))
CS = plt.contourf(X, Y, np.sign(Z), 200, cmap='jet', alpha=.2)
plt.contour(X, Y, Z, colors=['k', 'k', 'k'], linestyles=['--', '-', '--'], levels=[-.5, 0, .5])
plt.title(kernel, fontsize=15)
plt.xlim(x_min, x_max)
plt.ylim(y_min, y_max)
fignum = fignum + 1
plt.show()
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Ví dụ 1 - nhận dạng chữ số viết tay với SVM
Một số mẫu chữ số viết tay
Ví dụ 1 - nhận dạng chữ số viết tay với SVM
Đọc và chuẩn hóa dữ liệu
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import warnings
warnings.filterwarnings('ignore')
# import API functions
from keras.datasets import mnist
(X_train,y_train),(X_test,y_test) = mnist.load_data()
# get the image parameters
num_train_samples = X_train.shape[0] # 60000
num_test_samples = X_test.shape[0] # 10000
height = X_train.shape[1] # 28
width = X_train.shape[2] # 28
# normalize the data samples
X_train = X_train.reshape(num_train_samples, height*width) # 28x28 -> 784x1
X_train = X_train.astype('float32') / 255 # convert values to [0,1]
X_test = X_test.reshape(num_test_samples, height*width) # 28x28 -> 784x1
X_test = X_test.astype('float32') / 255 # convert values to [0,1]
Ví dụ 1 - nhận dạng chữ số viết tay với SVM
Tìm tham số C
from sklearn.svm import SVC
from sklearn.metrics import accuracy_score
# determine c
X_train_accuracy = []
X_test_accuracy = []
for c in [0.001,0.01,0.1,1,10]:
model = SVC(kernel= 'linear', C=c)
model.fit(X_train, y_train)
y_train_pred = model.predict(X_train)
y_test_pred = model.predict(X_test)
X_train_accuracy.append(accuracy_score(y_train, y_train_pred))
X_test_accuracy.append(accuracy_score(y_test, y_test_pred))
# plot for determining c
c = [0.001,0.01,0.1,1,10]
import matplotlib.pyplot as plt
plt.subplots(figsize=(10, 5))
plt.semilogx(c, X_train_accuracy,'-gD', color = 'blue', label="Training Accuracy")
plt.semilogx(c, X_test_accuracy,'-gD', color='red' , label="Testing Accuracy")
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Ví dụ 1 - nhận dạng chữ số viết tay với SVM
Vẽ tỷ lệ nhận dạng theo tham số C, nhận dạng với C tìm được
plt.grid(True)
plt.xlabel("Cost Parameter C",fontsize=14)
plt.ylabel("Accuracy",fontsize=14)
plt.legend()
plt.title('Accuracy versus the Cost Parameter C (log-scale)')
plt.show()
# run for c = 0.1
c = 0.1
model = SVC(kernel= 'linear', C=c)
model.fit(X_train, y_train)
# predict
y_train_pred = model.predict(X_train)
y_test_pred = model.predict(X_test)
# accuracy
X_train_accuracy = accuracy_score(y_train, y_train_pred)
X_test_accuracy = accuracy_score(y_test, y_test_pred)
#
print(X_train_accuracy)
print(X_test_accuracy)
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
Tỷ lệ nhận dạng tập huấn luyện: 95.87%
Tỷ lệ nhận dạng tập kiểm tra: 94.72%
Ví dụ 2- nhận dạng ảnh mặt người với SVM
Cho 2 thư mục ifd-train và ifd-test chứa các ảnh mặt người của 61
người, trong đó:
Thư mục ifd-train chứa ảnh dùng để huấn luyện và thư mục ifd-test dùng chứa
các ảnh nhận dạng.
Tên tệp trong 2 thư mục chứa một dấu ’-’ và các ký tự trước dấu ’-’ biểu diễn lớp
dữ liệu của ảnh, các ký tự sau dấu ’-’ là số thứ tự hnh ảnh mặt của mỗi người.
Ví dụ 2- nhận dạng ảnh mặt người với SVM
Đọc dữ liệu huấn luyện Đọc dữ liệu kiểm tra
import numpy as np
import glob
from PIL import Image
# read the train images
train_dir = 'ifd-train/'
num_classes = 61
X_train = []
y_train = []
for i in range(1,num_classes + 1):
filenames = train_dir + str(i) + '-*.jpg'
for filename in glob.glob(filenames):
y_train.append(i-1)
image = Image.open(filename)
X_train.append(np.array(image))
X_train = np.array(X_train)
y_train = np.array(y_train)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# read the test images
test_dir = 'ifd-test/'
X_test = []
y_test = []
for i in range(1,num_classes + 1):
filenames = test_dir + str(i) + '-*.jpg'
for filename in glob.glob(filenames):
y_test.append(i-1)
image = Image.open(filename)
X_test.append(np.array(image))
X_test = np.array(X_test)
y_test = np.array(y_test)
17
18
19
20
21
22
23
24
25
26
27
28
Ví dụ 2- nhận dạng ảnh mặt người với SVM
Chuẩn hóa dữ liệu
# create random rows
r = np.arange(0,len(y_train))
np.random.shuffle(r)
X_train = X_train[r,:]
y_train = y_train[r]
# get the image parameters
num_train_samples = X_train.shape[0]
num_test_samples = X_test.shape[0]
height = X_train.shape[1]
width = X_train.shape[2]
# normalize the data samples
X_train = X_train.reshape(num_train_samples, height*width)
X_train = X_train.astype('float32') / 255
X_test = X_test.reshape(num_test_samples, height*width)
X_test = X_test.astype('float32') / 255
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
Ví dụ 2- nhận dạng ảnh mặt người với SVM
Tìm tham số C
from sklearn.svm import SVC
from sklearn.metrics import accuracy_score
X_train_accuracy = []
X_test_accuracy = []
for c in [0.0001,0.001,0.01,0.1,1,10,100,1000,10000]:
model = SVC(kernel= 'linear', C=c)
model.fit(X_train, y_train)
y_train_pred = model.predict(X_train)
y_test_pred = model.predict(X_test)
X_train_accuracy.append(accuracy_score(y_train, y_train_pred))
X_test_accuracy.append(accuracy_score(y_test, y_test_pred))
# plot for determining c
c = [0.0001,0.001,0.01,0.1,1,10,100,1000,10000]
import matplotlib.pyplot as plt
plt.subplots(figsize=(10, 5))
plt.semilogx(c, X_train_accuracy,'-gD', color = 'blue', label="Training Accuracy")
plt.semilogx(c, X_test_accuracy,'-gD', color='red' , label="Testing Accuracy")
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
Ví dụ 2- nhận dạng ảnh mặt người với SVM
Vẽ tỷ lệ nhận dạng theo tham số C
Tỷ lệ nhận dạng tập huấn luyện: 100%
Tỷ lệ nhận dạng tập kiểm tra: 90.16%
plt.grid(True)
plt.xlabel("Cost Parameter C",fontsize=14)
plt.ylabel("Accuracy",fontsize=14)
plt.legend()
plt.title('Accuracy versus the Cost Parameter C (log-scale)')
plt.show()
# run for c = 0.1
c = 0.1
model = SVC(kernel= 'linear', C=c)
model.fit(X_train, y_train)
# predict
y_train_pred = model.predict(X_train)
y_test_pred = model.predict(X_test)
# accuracy
X_train_accuracy = accuracy_score(y_train, y_train_pred)
X_test_accuracy = accuracy_score(y_test, y_test_pred)
#
print(X_train_accuracy)
print(X_test_accuracy)
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
Bài tập
Nhận dạng chữ ký viết tay
Phụ lục A – khoảng cách từ một điểm đến siêu phẳng
Cho siêu phẳng
,
, khi vector vuông góc
với siêu phẳng
.
Giải sử 2 điểm
và
nằm trên siêu phẳng, khi
đó ta có:
Tức là
, điều này có nghĩa rằng
vector vuông góc với siêu phẳng.
2
1
Phụ lục A – khoảng cách từ một điểm đến siêu phẳng
Khoảng cách từ điểm
đến một siêu phẳng
,
Vector vuông góc với siêu phẳng
.
Vector cùng hướng với vector , do đó hướng
của vector là:
.
Chiều dài của vecor là , do đó vector được
xác định là:
Xét điểm ký hiệu bởi hình vuông, ta có:
.
Vì là điểm trên siêu phằng, nên
.
Phụ lục A – khoảng cách từ một điểm đến siêu phẳng
Thay vào
, ta có:
, tức là
Nếu xét điểm ký hiệu bởi hình tròn, ta có:
. Tương tự ta có:
Khoảng cách từ đến
:
Phụ lục B – Phương pháp Lagrangian Multiplers
Xem tài liệu
